/*
需求:
    从数组中, 找出最大的10个数
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 方法二：最小堆法
vector<int> findTop10ByHeap(const vector<int>& arr)
{
    int n = arr.size();
    if (n <= 10) {
        return arr;
    }

    // 定义最小堆（默认是最大堆，需用greater<int>）
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for (int num : arr) {
        if (minHeap.size() < 10) {
            // 堆未满，直接插入
            minHeap.push(num);
        }
        else {
            // 堆已满，若当前元素大于堆顶（最小元素），则替换
            if (num > minHeap.top()) {
                minHeap.pop();
                minHeap.push(num);
            }
        }
    }

    // 将堆中元素转换为vector
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }

    // 此时result是从小到大排序的，如需从大到小可反转
    reverse(result.begin(), result.end());
    return result;
}

// 示例用法
int main() {
    std::vector<int> large_array = { 22,55,33,11,44,66,77,88,99,10,12,36,14,56,16,95,18,69,20,5 };
    std::vector<int> top10 = findTop10ByHeap(large_array);
    for (int num : top10) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}